package com.explorati.MaxHeap.leetcode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 347. Top K Frequent Elements
 * 
 * Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input:
 * nums = [1], k = 1
 * 
 * @author explorati
 *
 */
class Solution {
	private class Freq implements Comparable<Freq> {
		int e, freq;

		public Freq(int e, int freq) {
			this.e = e;
			this.freq = freq;
		}

		public int compareTo(Freq another) {
			if (this.freq > another.freq) {
				return 1;
			} else if (this.freq < another.freq) {
				return -1;
			} else {
				return 0;
			}
		}
		// 内部存储规则，最小堆
		// public int compareTo(Freq another) {
		// // 越小优先级越高
		// if (this.freq < another.freq) {
		// return 1;
		// } else if (this.freq > another.freq) {
		// return -1;
		// } else {
		// return 0;
		// }
		// }
	}

	public List<Integer> topKFrequent(int[] nums, int k) {
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int num : nums) {
			if (map.containsKey(num)) {
				map.put(num, map.get(num) + 1);
			} else {
				map.put(num, 1);
			}
		}

		// Java实现的优先队列是最小堆的
		PriorityQueue<Freq> pq = new PriorityQueue<Freq>();
		for (int key : map.keySet()) {
			// 如果没有达到相应个数，则添加
			if (pq.size() < k)
				pq.add(new Freq(key, map.get(key)));
			else if (map.get(key) > pq.peek().freq) {
				pq.remove();
				pq.add(new Freq(key, map.get(key)));
			}
		}

		LinkedList<Integer> res = new LinkedList<Integer>();
		while (!pq.isEmpty()) {
			res.add(pq.remove().e);
		}
		return res;
	}
}
